/******************************************************************************
  contrib/cube/cube.c

  此文件包含可以绑定到 Postgres 后端的例程，并在处理查询的过程中被后端调用。这些例程的调用格式由 Postgres 架构决定。
******************************************************************************/

#include "postgres.h"

#include <math.h>

#include "access/gist.h"
#include "access/stratnum.h"
#include "cubedata.h"
#include "libpq/pqformat.h"
#include "utils/array.h"
#include "utils/float.h"

PG_MODULE_MAGIC;

/*
 * 来自 intarray contrib 头文件
 */
#define ARRPTR(x)  ( (double *) ARR_DATA_PTR(x) )
#define ARRNELEMS(x)  ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x))

/*
** 输入/输出例程
*/
PG_FUNCTION_INFO_V1(cube_in);
PG_FUNCTION_INFO_V1(cube_a_f8_f8);
PG_FUNCTION_INFO_V1(cube_a_f8);
PG_FUNCTION_INFO_V1(cube_out);
PG_FUNCTION_INFO_V1(cube_send);
PG_FUNCTION_INFO_V1(cube_recv);
PG_FUNCTION_INFO_V1(cube_f8);
PG_FUNCTION_INFO_V1(cube_f8_f8);
PG_FUNCTION_INFO_V1(cube_c_f8);
PG_FUNCTION_INFO_V1(cube_c_f8_f8);
PG_FUNCTION_INFO_V1(cube_dim);
PG_FUNCTION_INFO_V1(cube_ll_coord);
PG_FUNCTION_INFO_V1(cube_ur_coord);
PG_FUNCTION_INFO_V1(cube_coord);
PG_FUNCTION_INFO_V1(cube_coord_llur);
PG_FUNCTION_INFO_V1(cube_subset);

/*
** GiST 支持方法
*/

PG_FUNCTION_INFO_V1(g_cube_consistent);
PG_FUNCTION_INFO_V1(g_cube_compress);
PG_FUNCTION_INFO_V1(g_cube_decompress);
PG_FUNCTION_INFO_V1(g_cube_penalty);
PG_FUNCTION_INFO_V1(g_cube_picksplit);
PG_FUNCTION_INFO_V1(g_cube_union);
PG_FUNCTION_INFO_V1(g_cube_same);
PG_FUNCTION_INFO_V1(g_cube_distance);

/*
** B-tree 支持函数
*/
PG_FUNCTION_INFO_V1(cube_eq);
PG_FUNCTION_INFO_V1(cube_ne);
PG_FUNCTION_INFO_V1(cube_lt);
PG_FUNCTION_INFO_V1(cube_gt);
PG_FUNCTION_INFO_V1(cube_le);
PG_FUNCTION_INFO_V1(cube_ge);
PG_FUNCTION_INFO_V1(cube_cmp);

/*
** R-tree 支持函数
*/

PG_FUNCTION_INFO_V1(cube_contains);
PG_FUNCTION_INFO_V1(cube_contained);
PG_FUNCTION_INFO_V1(cube_overlap);
PG_FUNCTION_INFO_V1(cube_union);
PG_FUNCTION_INFO_V1(cube_inter);
PG_FUNCTION_INFO_V1(cube_size);

/*
** 杂项
*/
PG_FUNCTION_INFO_V1(distance_taxicab);
PG_FUNCTION_INFO_V1(cube_distance);
PG_FUNCTION_INFO_V1(distance_chebyshev);
PG_FUNCTION_INFO_V1(cube_is_point);
PG_FUNCTION_INFO_V1(cube_enlarge);

/*
** 仅供内部使用
*/
int32		cube_cmp_v0(NDBOX *fc_a, NDBOX *fc_b);
bool		cube_contains_v0(NDBOX *fc_a, NDBOX *fc_b);
bool		cube_overlap_v0(NDBOX *fc_a, NDBOX *fc_b);
NDBOX	   *cube_union_v0(NDBOX *fc_a, NDBOX *fc_b);
void		rt_cube_size(NDBOX *fc_a, double *fc_sz);
NDBOX	   *g_cube_binary_union(NDBOX *fc_r1, NDBOX *fc_r2, int *fc_sizep);
bool		g_cube_leaf_consistent(NDBOX *fc_key, NDBOX *fc_query, StrategyNumber fc_strategy);
bool		g_cube_internal_consistent(NDBOX *fc_key, NDBOX *fc_query, StrategyNumber fc_strategy);

/*
** 辅助函数
*/
static double fc_distance_1D(double fc_a1, double fc_a2, double fc_b1, double fc_b2);
static bool fc_cube_is_point_internal(NDBOX *fc_cube);


/*****************************************************************************
 * 输入/输出函数
 *****************************************************************************/

/* NdBox = [(lowerleft),(upperright)] */
/* [(xLL(1)...xLL(N)),(xUR(1)...xUR(n))] */
Datum cube_in(PG_FUNCTION_ARGS)
{
	char	   *fc_str = PG_GETARG_CSTRING(0);
	NDBOX	   *fc_result;

	cube_scanner_init(fc_str);

	if (cube_yyparse(&fc_result) != 0)
		cube_yyerror(&fc_result, "cube parser failed");

	cube_scanner_finish();

	PG_RETURN_NDBOX_P(fc_result);
}


/*
** 允许从 2 个 float[] 构建一个立方体
*/
Datum cube_a_f8_f8(PG_FUNCTION_ARGS)
{
	ArrayType  *fc_ur = PG_GETARG_ARRAYTYPE_P(0);
	ArrayType  *fc_ll = PG_GETARG_ARRAYTYPE_P(1);
	NDBOX	   *fc_result;
	int			fc_i;
	int			fc_dim;
	int			fc_size;
	bool		fc_point;
	double	   *fc_dur,
			   *fc_dll;

	if (array_contains_nulls(fc_ur) || array_contains_nulls(fc_ll))
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
				 errmsg("cannot work with arrays containing NULLs")));

	fc_dim = ARRNELEMS(fc_ur);
	if (fc_dim > CUBE_MAX_DIM)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("can't extend cube"),
				 errdetail("A cube cannot have more than %d dimensions.",
						   CUBE_MAX_DIM)));

	if (ARRNELEMS(fc_ll) != fc_dim)
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
				 errmsg("UR and LL arrays must be of same length")));

	fc_dur = ARRPTR(fc_ur);
	fc_dll = ARRPTR(fc_ll);

	/* 检查它是否是一个点 */
	fc_point = true;
	for (fc_i = 0; fc_i < fc_dim; fc_i++)
	{
		if (fc_dur[fc_i] != fc_dll[fc_i])
		{
			fc_point = false;
			break;
		}
	}

	fc_size = fc_point ? POINT_SIZE(fc_dim) : CUBE_SIZE(fc_dim);
	fc_result = (NDBOX *) palloc0(fc_size);
	SET_VARSIZE(fc_result, fc_size);
	SET_DIM(fc_result, fc_dim);

	for (fc_i = 0; fc_i < fc_dim; fc_i++)
		fc_result->x[fc_i] = fc_dur[fc_i];

	if (!fc_point)
	{
		for (fc_i = 0; fc_i < fc_dim; fc_i++)
			fc_result->x[fc_i + fc_dim] = fc_dll[fc_i];
	}
	else
		SET_POINT_BIT(fc_result);

	PG_RETURN_NDBOX_P(fc_result);
}

/*
** 允许从 float[] 构建一个零体积立方体
*/
Datum cube_a_f8(PG_FUNCTION_ARGS)
{
	ArrayType  *fc_ur = PG_GETARG_ARRAYTYPE_P(0);
	NDBOX	   *fc_result;
	int			fc_i;
	int			fc_dim;
	int			fc_size;
	double	   *fc_dur;

	if (array_contains_nulls(fc_ur))
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
				 errmsg("cannot work with arrays containing NULLs")));

	fc_dim = ARRNELEMS(fc_ur);
	if (fc_dim > CUBE_MAX_DIM)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("array is too long"),
				 errdetail("A cube cannot have more than %d dimensions.",
						   CUBE_MAX_DIM)));

	fc_dur = ARRPTR(fc_ur);

	fc_size = POINT_SIZE(fc_dim);
	fc_result = (NDBOX *) palloc0(fc_size);
	SET_VARSIZE(fc_result, fc_size);
	SET_DIM(fc_result, fc_dim);
	SET_POINT_BIT(fc_result);

	for (fc_i = 0; fc_i < fc_dim; fc_i++)
		fc_result->x[fc_i] = fc_dur[fc_i];

	PG_RETURN_NDBOX_P(fc_result);
}

Datum cube_subset(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_c = PG_GETARG_NDBOX_P(0);
	ArrayType  *fc_idx = PG_GETARG_ARRAYTYPE_P(1);
	NDBOX	   *fc_result;
	int			fc_size,
				fc_dim,
				fc_i;
	int		   *fc_dx;

	if (array_contains_nulls(fc_idx))
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
				 errmsg("cannot work with arrays containing NULLs")));

	fc_dx = (int32 *) ARR_DATA_PTR(fc_idx);

	fc_dim = ARRNELEMS(fc_idx);
	if (fc_dim > CUBE_MAX_DIM)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("array is too long"),
				 errdetail("A cube cannot have more than %d dimensions.",
						   CUBE_MAX_DIM)));

	fc_size = IS_POINT(fc_c) ? POINT_SIZE(fc_dim) : CUBE_SIZE(fc_dim);
	fc_result = (NDBOX *) palloc0(fc_size);
	SET_VARSIZE(fc_result, fc_size);
	SET_DIM(fc_result, fc_dim);

	if (IS_POINT(fc_c))
		SET_POINT_BIT(fc_result);

	for (fc_i = 0; fc_i < fc_dim; fc_i++)
	{
		if ((fc_dx[fc_i] <= 0) || (fc_dx[fc_i] > DIM(fc_c)))
#ifdef FDD //cppcheck
		{
#endif
			ereport(ERROR,
					(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
					 errmsg("Index out of bounds")));
#ifdef FDD //cppcheck
			PG_RETURN_VOID();
		}
#endif
		fc_result->x[fc_i] = fc_c->x[fc_dx[fc_i] - 1];
		if (!IS_POINT(fc_c))
			fc_result->x[fc_i + fc_dim] = fc_c->x[fc_dx[fc_i] + DIM(fc_c) - 1];
	}

	PG_FREE_IF_COPY(fc_c, 0);
	PG_RETURN_NDBOX_P(fc_result);
}

Datum cube_out(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_cube = PG_GETARG_NDBOX_P(0);
	StringInfoData fc_buf;
	int			fc_dim = DIM(fc_cube);
	int			fc_i;

	initStringInfo(&fc_buf);

	appendStringInfoChar(&fc_buf, '(');
	for (fc_i = 0; fc_i < fc_dim; fc_i++)
	{
		if (fc_i > 0)
			appendStringInfoString(&fc_buf, ", ");
		appendStringInfoString(&fc_buf, float8out_internal(LL_COORD(fc_cube, fc_i)));
	}
	appendStringInfoChar(&fc_buf, ')');

	if (!fc_cube_is_point_internal(fc_cube))
	{
		appendStringInfoString(&fc_buf, ",(");
		for (fc_i = 0; fc_i < fc_dim; fc_i++)
		{
			if (fc_i > 0)
				appendStringInfoString(&fc_buf, ", ");
			appendStringInfoString(&fc_buf, float8out_internal(UR_COORD(fc_cube, fc_i)));
		}
		appendStringInfoChar(&fc_buf, ')');
	}

	PG_FREE_IF_COPY(fc_cube, 0);
	PG_RETURN_CSTRING(fc_buf.data);
}

/*
 * cube_send - cube 类型的二进制输出处理程序
 */
Datum cube_send(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_cube = PG_GETARG_NDBOX_P(0);
	StringInfoData fc_buf;
	int32		fc_i,
				fc_nitems = DIM(fc_cube);

	pq_begintypsend(&fc_buf);
	pq_sendint32(&fc_buf, fc_cube->header);
	if (!IS_POINT(fc_cube))
		fc_nitems += fc_nitems;
	/* 为了与 cube_recv 对称，我们在这里不使用 LL_COORD/UR_COORD */
	for (fc_i = 0; fc_i < fc_nitems; fc_i++)
		pq_sendfloat8(&fc_buf, fc_cube->x[fc_i]);

	PG_RETURN_BYTEA_P(pq_endtypsend(&fc_buf));
}

/*
 * cube_recv - cube 类型的二进制输入处理程序
 */
Datum cube_recv(PG_FUNCTION_ARGS)
{
	StringInfo	fc_buf = (StringInfo) PG_GETARG_POINTER(0);
	int32		fc_header;
	int32		fc_i,
				fc_nitems;
	NDBOX	   *fc_cube;

	fc_header = pq_getmsgint(fc_buf, sizeof(int32));
	fc_nitems = (fc_header & DIM_MASK);
	if (fc_nitems > CUBE_MAX_DIM)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("cube dimension is too large"),
				 errdetail("A cube cannot have more than %d dimensions.",
						   CUBE_MAX_DIM)));
	if ((fc_header & POINT_BIT) == 0)
		fc_nitems += fc_nitems;
	fc_cube = palloc(offsetof(NDBOX, x) + sizeof(double) * fc_nitems);
	SET_VARSIZE(fc_cube, offsetof(NDBOX, x) + sizeof(double) * fc_nitems);
	fc_cube->header = fc_header;
	for (fc_i = 0; fc_i < fc_nitems; fc_i++)
		fc_cube->x[fc_i] = pq_getmsgfloat8(fc_buf);

	PG_RETURN_NDBOX_P(fc_cube);
}


/*****************************************************************************
 *						   GiST 函数
 *****************************************************************************/

/*
** 用于盒子的 GiST 一致性方法
** 如果对于所有数据项 x 小于条目，谓词 x op 查询 == false，则应返回 false，
** 其中 op 是对应于 pg_amop 表中策略的操作。
*/
Datum g_cube_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	NDBOX	   *fc_query = PG_GETARG_NDBOX_P(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	bool		fc_res;

	/* 由此函数服务的所有案例都是精确的 */
	*fc_recheck = false;

	/*
	 * 如果条目不是叶子，则使用 g_cube_internal_consistent，否则使用
	 * g_cube_leaf_consistent
	 */
	if (GIST_LEAF(fc_entry))
		fc_res = g_cube_leaf_consistent(DatumGetNDBOXP(fc_entry->key),
									 fc_query, fc_strategy);
	else
		fc_res = g_cube_internal_consistent(DatumGetNDBOXP(fc_entry->key),
										 fc_query, fc_strategy);

	PG_FREE_IF_COPY(fc_query, 1);
	PG_RETURN_BOOL(fc_res);
}


/*
** 用于盒子的 GiST 联合方法
** 返回包围 entryvec 中所有条目的最小包围盒
*/
Datum g_cube_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	int		   *fc_sizep = (int *) PG_GETARG_POINTER(1);
	NDBOX	   *fc_out = (NDBOX *) NULL;
	NDBOX	   *fc_tmp;
	int			fc_i;

	fc_tmp = DatumGetNDBOXP(fc_entryvec->vector[0].key);

	/*
	 * sizep = sizeof(NDBOX); -- NDBOX 具有可变大小
	 */
	*fc_sizep = VARSIZE(fc_tmp);

	for (fc_i = 1; fc_i < fc_entryvec->n; fc_i++)
	{
		fc_out = g_cube_binary_union(fc_tmp,
								  DatumGetNDBOXP(fc_entryvec->vector[fc_i].key),
								  fc_sizep);
		fc_tmp = fc_out;
	}

	PG_RETURN_POINTER(fc_out);
}

/*
** 用于盒子的 GiST 压缩和解压缩方法
** 不执行任何操作。
*/

Datum g_cube_compress(PG_FUNCTION_ARGS)
{
	PG_RETURN_DATUM(PG_GETARG_DATUM(0));
}

Datum g_cube_decompress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	NDBOX	   *fc_key = DatumGetNDBOXP(fc_entry->key);

	if (fc_key != DatumGetNDBOXP(fc_entry->key))
	{
		GISTENTRY  *fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));

		gistentryinit(*fc_retval, PointerGetDatum(fc_key),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
		PG_RETURN_POINTER(fc_retval);
	}
	PG_RETURN_POINTER(fc_entry);
}


/*
** 用于盒子的 GiST 惩罚方法
** 与 R-tree 论文中的一样，我们使用面积变化作为我们的惩罚指标
*/
Datum g_cube_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_result = (float *) PG_GETARG_POINTER(2);
	NDBOX	   *fc_ud;
	double		fc_tmp1,
				fc_tmp2;

	fc_ud = cube_union_v0(DatumGetNDBOXP(fc_origentry->key),
					   DatumGetNDBOXP(fc_newentry->key));
	rt_cube_size(fc_ud, &fc_tmp1);
	rt_cube_size(DatumGetNDBOXP(fc_origentry->key), &fc_tmp2);
	*fc_result = (float) (fc_tmp1 - fc_tmp2);

	PG_RETURN_FLOAT8(*fc_result);
}



/*
** 用于盒子的 GiST PickSplit 方法
** 我们使用 Guttman 的多项式时间分割算法
*/
Datum g_cube_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	OffsetNumber fc_i,
				fc_j;
	NDBOX	   *fc_datum_alpha,
			   *fc_datum_beta;
	NDBOX	   *fc_datum_l,
			   *fc_datum_r;
	NDBOX	   *fc_union_d,
			   *fc_union_dl,
			   *fc_union_dr;
	NDBOX	   *fc_inter_d;
	bool		fc_firsttime;
	double		fc_size_alpha,
				fc_size_beta,
				fc_size_union,
				fc_size_inter;
	double		fc_size_waste,
				fc_waste;
	double		fc_size_l,
				fc_size_r;
	int			fc_nbytes;
	OffsetNumber fc_seed_1 = 1,
				fc_seed_2 = 2;
	OffsetNumber *fc_left,
			   *fc_right;
	OffsetNumber fc_maxoff;

	fc_maxoff = fc_entryvec->n - 2;
	fc_nbytes = (fc_maxoff + 2) * sizeof(OffsetNumber);
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);

	fc_firsttime = true;
	fc_waste = 0.0;

	for (fc_i = FirstOffsetNumber; fc_i < fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		fc_datum_alpha = DatumGetNDBOXP(fc_entryvec->vector[fc_i].key);
		for (fc_j = OffsetNumberNext(fc_i); fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
		{
			fc_datum_beta = DatumGetNDBOXP(fc_entryvec->vector[fc_j].key);

			/* 通过合并这些来计算浪费的空间 */
			/* size_waste = size_union - size_inter; */
			fc_union_d = cube_union_v0(fc_datum_alpha, fc_datum_beta);
			rt_cube_size(fc_union_d, &fc_size_union);
			fc_inter_d = DatumGetNDBOXP(DirectFunctionCall2(cube_inter,
														 fc_entryvec->vector[fc_i].key,
														 fc_entryvec->vector[fc_j].key));
			rt_cube_size(fc_inter_d, &fc_size_inter);
			fc_size_waste = fc_size_union - fc_size_inter;

			/*
			 * 这些比我们已经看到的切分更有前景吗？
			 */

			if (fc_size_waste > fc_waste || fc_firsttime)
			{
				fc_waste = fc_size_waste;
				fc_seed_1 = fc_i;
				fc_seed_2 = fc_j;
				fc_firsttime = false;
			}
		}
	}

	fc_left = fc_v->spl_left;
	fc_v->spl_nleft = 0;
	fc_right = fc_v->spl_right;
	fc_v->spl_nright = 0;

	fc_datum_alpha = DatumGetNDBOXP(fc_entryvec->vector[fc_seed_1].key);
	fc_datum_l = cube_union_v0(fc_datum_alpha, fc_datum_alpha);
	rt_cube_size(fc_datum_l, &fc_size_l);
	fc_datum_beta = DatumGetNDBOXP(fc_entryvec->vector[fc_seed_2].key);
	fc_datum_r = cube_union_v0(fc_datum_beta, fc_datum_beta);
	rt_cube_size(fc_datum_r, &fc_size_r);

	/*
	 * 现在将区域在两个种子之间分开。该分割算法的一个重要特性是，分割向量 v 在其左向量和右向量中按顺序包含要分割的项的索引。我们在实际分割页面的代码中利用了这个特性进行合并。
	 *
	 * 为了提高效率，我们还将在此循环中放置新的索引元组。这在最后处理，当我们放置了所有现有元组且 i == maxoff + 1 时。
	 */

	fc_maxoff = OffsetNumberNext(fc_maxoff);
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		/*
		 * 如果我们已经决定将此项放置在哪里，则直接放到右侧列表。否则，我们需要弄清楚哪个页面需要最少的扩展以存储该项。
		 */

		if (fc_i == fc_seed_1)
		{
			*fc_left++ = fc_i;
			fc_v->spl_nleft++;
			continue;
		}
		else if (fc_i == fc_seed_2)
		{
			*fc_right++ = fc_i;
			fc_v->spl_nright++;
			continue;
		}

		/* 好吧，哪个页面需要最少的扩展？ */
		fc_datum_alpha = DatumGetNDBOXP(fc_entryvec->vector[fc_i].key);
		fc_union_dl = cube_union_v0(fc_datum_l, fc_datum_alpha);
		fc_union_dr = cube_union_v0(fc_datum_r, fc_datum_alpha);
		rt_cube_size(fc_union_dl, &fc_size_alpha);
		rt_cube_size(fc_union_dr, &fc_size_beta);

		/* 选择将其添加到哪个页面 */
		if (fc_size_alpha - fc_size_l < fc_size_beta - fc_size_r)
		{
			fc_datum_l = fc_union_dl;
			fc_size_l = fc_size_alpha;
			*fc_left++ = fc_i;
			fc_v->spl_nleft++;
		}
		else
		{
			fc_datum_r = fc_union_dr;
			fc_size_r = fc_size_beta;
			*fc_right++ = fc_i;
			fc_v->spl_nright++;
		}
	}
	*fc_left = *fc_right = FirstOffsetNumber; /* 哨兵值 */

	fc_v->spl_ldatum = PointerGetDatum(fc_datum_l);
	fc_v->spl_rdatum = PointerGetDatum(fc_datum_r);

	PG_RETURN_POINTER(fc_v);
}

/*
** 等式方法
*/
Datum g_cube_same(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_b1 = PG_GETARG_NDBOX_P(0);
	NDBOX	   *fc_b2 = PG_GETARG_NDBOX_P(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);

	if (cube_cmp_v0(fc_b1, fc_b2) == 0)
		*fc_result = true;
	else
		*fc_result = false;

	PG_RETURN_NDBOX_P(fc_result);
}

/*
** 支持例程
*/
bool g_cube_leaf_consistent(NDBOX *fc_key,
					   NDBOX *fc_query,
					   StrategyNumber fc_strategy)
{
	bool		fc_retval;

	switch (fc_strategy)
	{
		case RTOverlapStrategyNumber:
			fc_retval = cube_overlap_v0(fc_key, fc_query);
			break;
		case RTSameStrategyNumber:
			fc_retval = (cube_cmp_v0(fc_key, fc_query) == 0);
			break;
		case RTContainsStrategyNumber:
		case RTOldContainsStrategyNumber:
			fc_retval = cube_contains_v0(fc_key, fc_query);
			break;
		case RTContainedByStrategyNumber:
		case RTOldContainedByStrategyNumber:
			fc_retval = cube_contains_v0(fc_query, fc_key);
			break;
		default:
			fc_retval = false;
	}
	return fc_retval;
}

bool g_cube_internal_consistent(NDBOX *fc_key,
						   NDBOX *fc_query,
						   StrategyNumber fc_strategy)
{
	bool		fc_retval;

	switch (fc_strategy)
	{
		case RTOverlapStrategyNumber:
			fc_retval = (bool) cube_overlap_v0(fc_key, fc_query);
			break;
		case RTSameStrategyNumber:
		case RTContainsStrategyNumber:
		case RTOldContainsStrategyNumber:
			fc_retval = (bool) cube_contains_v0(fc_key, fc_query);
			break;
		case RTContainedByStrategyNumber:
		case RTOldContainedByStrategyNumber:
			fc_retval = (bool) cube_overlap_v0(fc_key, fc_query);
			break;
		default:
			fc_retval = false;
	}
	return fc_retval;
}

NDBOX *
g_cube_binary_union(NDBOX *fc_r1, NDBOX *fc_r2, int *fc_sizep)
{
	NDBOX	   *fc_retval;

	fc_retval = cube_union_v0(fc_r1, fc_r2);
	*fc_sizep = VARSIZE(fc_retval);

	return fc_retval;
}


/* cube_union_v0 */
NDBOX *
cube_union_v0(NDBOX *fc_a, NDBOX *fc_b)
{
	int			fc_i;
	NDBOX	   *fc_result;
	int			fc_dim;
	int			fc_size;

	/* 简单情况 */
	if (fc_a == fc_b)
		return fc_a;

	/* 如有必要，交换参数，以确保 'a' 总是大于 'b' */
	if (DIM(fc_a) < DIM(fc_b))
	{
		NDBOX	   *fc_tmp = fc_b;

		fc_b = fc_a;
		fc_a = fc_tmp;
	}
	fc_dim = DIM(fc_a);

	fc_size = CUBE_SIZE(fc_dim);
	fc_result = palloc0(fc_size);
	SET_VARSIZE(fc_result, fc_size);
	SET_DIM(fc_result, fc_dim);

	/* 首先计算两个参数中存在的维度的联合 */
	for (fc_i = 0; fc_i < DIM(fc_b); fc_i++)
	{
		fc_result->x[fc_i] = Min(Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)),
						   Min(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)));
		fc_result->x[fc_i + DIM(fc_a)] = Max(Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)),
									Max(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)));
	}
	/* 继续处理仅存在于 'a' 的更高维度 */
	for (; fc_i < DIM(fc_a); fc_i++)
	{
		fc_result->x[fc_i] = Min(0,
						   Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i))
			);
		fc_result->x[fc_i + fc_dim] = Max(0,
								 Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i))
			);
	}

	/*
	 * 检查结果是否实际上是一个点，并相应地在数据项中设置标志。
	 * （我们不费心将其重新分配得更小）
	 */
	if (fc_cube_is_point_internal(fc_result))
	{
		fc_size = POINT_SIZE(fc_dim);
		SET_VARSIZE(fc_result, fc_size);
		SET_POINT_BIT(fc_result);
	}

	return fc_result;
}

Datum cube_union(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0);
	NDBOX	   *fc_b = PG_GETARG_NDBOX_P(1);
	NDBOX	   *fc_res;

	fc_res = cube_union_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_NDBOX_P(fc_res);
}

/* cube_inter */
Datum cube_inter(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0);
	NDBOX	   *fc_b = PG_GETARG_NDBOX_P(1);
	NDBOX	   *fc_result;
	bool		fc_swapped = false;
	int			fc_i;
	int			fc_dim;
	int			fc_size;

	/* 如有必要，交换参数，以确保 'a' 总是大于 'b' */
	if (DIM(fc_a) < DIM(fc_b))
	{
		NDBOX	   *fc_tmp = fc_b;

		fc_b = fc_a;
		fc_a = fc_tmp;
		fc_swapped = true;
	}
	fc_dim = DIM(fc_a);

	fc_size = CUBE_SIZE(fc_dim);
	fc_result = (NDBOX *) palloc0(fc_size);
	SET_VARSIZE(fc_result, fc_size);
	SET_DIM(fc_result, fc_dim);

	/* 首先计算两个参数中存在的维度的交集 */
	for (fc_i = 0; fc_i < DIM(fc_b); fc_i++)
	{
		fc_result->x[fc_i] = Max(Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)),
						   Min(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)));
		fc_result->x[fc_i + DIM(fc_a)] = Min(Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)),
									Max(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)));
	}
	/* 继续处理仅存在于 'a' 的更高维度 */
	for (; fc_i < DIM(fc_a); fc_i++)
	{
		fc_result->x[fc_i] = Max(0,
						   Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i))
			);
		fc_result->x[fc_i + DIM(fc_a)] = Min(0,
									Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i))
			);
	}

	/*
	 * 检查结果是否实际上是一个点，并相应地在数据项中设置标志。
	 * （我们不费心将其重新分配得更小）
	 */
	if (fc_cube_is_point_internal(fc_result))
	{
		fc_size = POINT_SIZE(fc_dim);
		fc_result = repalloc(fc_result, fc_size);
		SET_VARSIZE(fc_result, fc_size);
		SET_POINT_BIT(fc_result);
	}

	if (fc_swapped)
	{
		PG_FREE_IF_COPY(fc_b, 0);
		PG_FREE_IF_COPY(fc_a, 1);
	}
	else
	{
		PG_FREE_IF_COPY(fc_a, 0);
		PG_FREE_IF_COPY(fc_b, 1);
	}

	/*
	 * 返回非空交集是否可以接受，用于不重叠的盒子？
	 */
	PG_RETURN_NDBOX_P(fc_result);
}

/* cube_size */
Datum cube_size(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0);
	double		fc_result;

	rt_cube_size(fc_a, &fc_result);
	PG_FREE_IF_COPY(fc_a, 0);
	PG_RETURN_FLOAT8(fc_result);
}

void rt_cube_size(NDBOX *fc_a, double *fc_size)
{
	double		fc_result;
	int			fc_i;

	if (fc_a == (NDBOX *) NULL)
	{
		/* GiST 的特殊情况 */
		fc_result = 0.0;
	}
	else if (IS_POINT(fc_a) || DIM(fc_a) == 0)
	{
		/* 必然大小为零 */
		fc_result = 0.0;
	}
	else
	{
		fc_result = 1.0;
		for (fc_i = 0; fc_i < DIM(fc_a); fc_i++)
			fc_result *= Abs(UR_COORD(fc_a, fc_i) - LL_COORD(fc_a, fc_i));
	}
	*fc_size = fc_result;
}

/* 创建一种度量，在该度量中，一个盒子将低于另一个盒子 
   -- 这对于排序和确定唯一性可能很有用 */
int32 cube_cmp_v0(NDBOX *fc_a, NDBOX *fc_b)
{
	int			fc_i;
	int			fc_dim;

	fc_dim = Min(DIM(fc_a), DIM(fc_b));

	/* 比较共同的维度 */
	for (fc_i = 0; fc_i < fc_dim; fc_i++)
	{
		if (Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) >
			Min(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)))
			return 1;
		if (Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) <
			Min(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)))
			return -1;
	}
	for (fc_i = 0; fc_i < fc_dim; fc_i++)
	{
		if (Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) >
			Max(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)))
			return 1;
		if (Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) <
			Max(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)))
			return -1;
	}

	/* 将额外的维度与零进行比较 */
	if (DIM(fc_a) > DIM(fc_b))
	{
		for (fc_i = fc_dim; fc_i < DIM(fc_a); fc_i++)
		{
			if (Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) > 0)
				return 1;
			if (Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) < 0)
				return -1;
		}
		for (fc_i = fc_dim; fc_i < DIM(fc_a); fc_i++)
		{
			if (Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) > 0)
				return 1;
			if (Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) < 0)
				return -1;
		}

		/*
		 * 如果所有共同维度相等，则更高维度的立方体取胜
		 */
		return 1;
	}
	if (DIM(fc_a) < DIM(fc_b))
	{
		for (fc_i = fc_dim; fc_i < DIM(fc_b); fc_i++)
		{
			if (Min(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)) > 0)
				return -1;
			if (Min(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)) < 0)
				return 1;
		}
		for (fc_i = fc_dim; fc_i < DIM(fc_b); fc_i++)
		{
			if (Max(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)) > 0)
				return -1;
			if (Max(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)) < 0)
				return 1;
		}

		/*
		 * 如果所有共同维度相等，则更高维度的立方体取胜
		 */
		return -1;
	}

	/* 它们实际上是相等的 */
	return 0;
}

Datum cube_cmp(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	int32		fc_res;

	fc_res = cube_cmp_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_INT32(fc_res);
}


Datum cube_eq(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	int32		fc_res;

	fc_res = cube_cmp_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res == 0);
}


Datum cube_ne(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	int32		fc_res;

	fc_res = cube_cmp_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res != 0);
}


Datum cube_lt(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	int32		fc_res;

	fc_res = cube_cmp_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res < 0);
}


Datum cube_gt(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	int32		fc_res;

	fc_res = cube_cmp_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res > 0);
}


Datum cube_le(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	int32		fc_res;

	fc_res = cube_cmp_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res <= 0);
}


Datum cube_ge(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	int32		fc_res;

	fc_res = cube_cmp_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res >= 0);
}


/* 包含 */
/* Box(A) 包含 Box(B) 当且仅当 pt(A) < pt(B) */
bool cube_contains_v0(NDBOX *fc_a, NDBOX *fc_b)
{
	int			fc_i;

	if ((fc_a == NULL) || (fc_b == NULL))
		return false;

	if (DIM(fc_a) < DIM(fc_b))
	{
		/*
		 * 进一步的比较是有意义的，如果 (b) 的多余维度为零。因为
		 * UL 和 UR 坐标必须为零，我们可以在不担心哪个是哪个的情况下检查它们所有。
		 */
		for (fc_i = DIM(fc_a); fc_i < DIM(fc_b); fc_i++)
		{
			if (LL_COORD(fc_b, fc_i) != 0)
				return false;
			if (UR_COORD(fc_b, fc_i) != 0)
				return false;
		}
	}

	/* 对 (a) 的额外维度没什么好关心的，若有的话 */
	for (fc_i = 0; fc_i < Min(DIM(fc_a), DIM(fc_b)); fc_i++)
	{
		if (Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) >
			Min(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)))
			return false;
		if (Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) <
			Max(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)))
			return false;
	}

	return true;
}

Datum cube_contains(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	bool		fc_res;

	fc_res = cube_contains_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res);
}

/* 被包含 */
/* Box(A) 被 Box(B) 包含 当且仅当 Box(B) 包含 Box(A) */
Datum cube_contained(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	bool		fc_res;

	fc_res = cube_contains_v0(fc_b, fc_a);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res);
}

/* 重叠 */
/* Box(A) 重叠 Box(B) 当且仅当 (pt(a)LL < pt(B)UR) && (pt(b)LL < pt(a)UR) */
bool cube_overlap_v0(NDBOX *fc_a, NDBOX *fc_b)
{
	int			fc_i;

	if ((fc_a == NULL) || (fc_b == NULL))
		return false;

	/* 如有必要，交换盒子指针 */
	if (DIM(fc_a) < DIM(fc_b))
	{
		NDBOX	   *fc_tmp = fc_b;

		fc_b = fc_a;
		fc_a = fc_tmp;
	}

	/* 在 (b) 的维度内进行比较 */
	for (fc_i = 0; fc_i < DIM(fc_b); fc_i++)
	{
		if (Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) > Max(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)))
			return false;
		if (Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) < Min(LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)))
			return false;
	}

	/* 将 (a) 中在 (b) 中缺失的维度与零进行比较 */
	for (fc_i = DIM(fc_b); fc_i < DIM(fc_a); fc_i++)
	{
		if (Min(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) > 0)
			return false;
		if (Max(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i)) < 0)
			return false;
	}

	return true;
}


Datum cube_overlap(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	bool		fc_res;

	fc_res = cube_overlap_v0(fc_a, fc_b);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_BOOL(fc_res);
}


/* 距离 */
/* 距离是通过对盒子在笛卡尔轴上的 1D 投影之间的平方距离进行每轴求和计算得出的。
   假设重叠投影之间的距离为零，这个度量与“常识”几何距离一致 */
Datum cube_distance(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	bool		fc_swapped = false;
	double		fc_d,
				fc_distance;
	int			fc_i;

	/* 如有必要，交换盒子指针 */
	if (DIM(fc_a) < DIM(fc_b))
	{
		NDBOX	   *fc_tmp = fc_b;

		fc_b = fc_a;
		fc_a = fc_tmp;
		fc_swapped = true;
	}

	fc_distance = 0.0;
	/* 在 (b) 的维度内进行计算 */
	for (fc_i = 0; fc_i < DIM(fc_b); fc_i++)
	{
		fc_d = fc_distance_1D(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i), LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i));
		fc_distance += fc_d * fc_d;
	}

	/* 对于 (b) 中缺失的 (a) 中那些维度，计算到零的距离 */
	for (fc_i = DIM(fc_b); fc_i < DIM(fc_a); fc_i++)
	{
		fc_d = fc_distance_1D(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i), 0.0, 0.0);
		fc_distance += fc_d * fc_d;
	}

	if (fc_swapped)
	{
		PG_FREE_IF_COPY(fc_b, 0);
		PG_FREE_IF_COPY(fc_a, 1);
	}
	else
	{
		PG_FREE_IF_COPY(fc_a, 0);
		PG_FREE_IF_COPY(fc_b, 1);
	}

	PG_RETURN_FLOAT8(sqrt(fc_distance));
}

Datum distance_taxicab(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	bool		fc_swapped = false;
	double		fc_distance;
	int			fc_i;

	/* 如有必要，交换盒子指针 */
	if (DIM(fc_a) < DIM(fc_b))
	{
		NDBOX	   *fc_tmp = fc_b;

		fc_b = fc_a;
		fc_a = fc_tmp;
		fc_swapped = true;
	}

	fc_distance = 0.0;
	/* 在 (b) 的维度内进行计算 */
	for (fc_i = 0; fc_i < DIM(fc_b); fc_i++)
		fc_distance += fabs(fc_distance_1D(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i),
									 LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)));

	/* 对于 (b) 中缺失的 (a) 中那些维度，计算到零的距离 */
	for (fc_i = DIM(fc_b); fc_i < DIM(fc_a); fc_i++)
		fc_distance += fabs(fc_distance_1D(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i),
									 0.0, 0.0));

	if (fc_swapped)
	{
		PG_FREE_IF_COPY(fc_b, 0);
		PG_FREE_IF_COPY(fc_a, 1);
	}
	else
	{
		PG_FREE_IF_COPY(fc_a, 0);
		PG_FREE_IF_COPY(fc_b, 1);
	}

	PG_RETURN_FLOAT8(fc_distance);
}

Datum distance_chebyshev(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0),
			   *fc_b = PG_GETARG_NDBOX_P(1);
	bool		fc_swapped = false;
	double		fc_d,
				fc_distance;
	int			fc_i;

	/* 如有必要，交换盒子指针 */
	if (DIM(fc_a) < DIM(fc_b))
	{
		NDBOX	   *fc_tmp = fc_b;

		fc_b = fc_a;
		fc_a = fc_tmp;
		fc_swapped = true;
	}

	fc_distance = 0.0;
	/* 在 (b) 的维度内进行计算 */
	for (fc_i = 0; fc_i < DIM(fc_b); fc_i++)
	{
		fc_d = fabs(fc_distance_1D(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i),
							 LL_COORD(fc_b, fc_i), UR_COORD(fc_b, fc_i)));
		if (fc_d > fc_distance)
			fc_distance = fc_d;
	}

	/* 对于 (b) 中缺失的 (a) 中那些维度，计算到零的距离 */
	for (fc_i = DIM(fc_b); fc_i < DIM(fc_a); fc_i++)
	{
		fc_d = fabs(fc_distance_1D(LL_COORD(fc_a, fc_i), UR_COORD(fc_a, fc_i), 0.0, 0.0));
		if (fc_d > fc_distance)
			fc_distance = fc_d;
	}

	if (fc_swapped)
	{
		PG_FREE_IF_COPY(fc_b, 0);
		PG_FREE_IF_COPY(fc_a, 1);
	}
	else
	{
		PG_FREE_IF_COPY(fc_a, 0);
		PG_FREE_IF_COPY(fc_b, 1);
	}

	PG_RETURN_FLOAT8(fc_distance);
}

Datum g_cube_distance(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);
	NDBOX	   *fc_cube = DatumGetNDBOXP(fc_entry->key);
	double		fc_retval;

	if (fc_strategy == CubeKNNDistanceCoord)
	{
		/*
		 * 通过 ~> 操作符处理排序。有关详细信息，请参见 cube_coord_llur() 的注释
		 */
		int			fc_coord = PG_GETARG_INT32(1);
		bool		fc_isLeaf = GistPageIsLeaf(fc_entry->page);
		bool		fc_inverse = false;

		/* 0 是唯一不支持的坐标值 */
		if (fc_coord == 0)
			ereport(ERROR,
					(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
					 errmsg("zero cube index is not defined")));

		/* 对于负坐标返回反向值 */
		if (fc_coord < 0)
		{
			fc_coord = -fc_coord;
			fc_inverse = true;
		}

		if (fc_coord <= 2 * DIM(fc_cube))
		{
			/* 维度索引 */
			int			fc_index = (fc_coord - 1) / 2;

			/* 这是否是上界（否则为下界） */
			bool		fc_upper = ((fc_coord - 1) % 2 == 1);

			if (IS_POINT(fc_cube))
			{
				fc_retval = fc_cube->x[fc_index];
			}
			else
			{
				if (fc_isLeaf)
				{
					/* 对于叶子节点，只需返回所需的上/下界 */
					if (fc_upper)
						fc_retval = Max(fc_cube->x[fc_index], fc_cube->x[fc_index + DIM(fc_cube)]);
					else
						fc_retval = Min(fc_cube->x[fc_index], fc_cube->x[fc_index + DIM(fc_cube)]);
				}
				else
				{
					/*
					 * 对于非叶子节点，我们应该始终返回下界，
					 * 因为子树中的子节点的上界可能与我们的下界一样小。
					 * 在反向情况下，我们返回上界，因为它变为反向值的下界。
					 */
					if (!fc_inverse)
						fc_retval = Min(fc_cube->x[fc_index], fc_cube->x[fc_index + DIM(fc_cube)]);
					else
						fc_retval = Max(fc_cube->x[fc_index], fc_cube->x[fc_index + DIM(fc_cube)]);
				}
			}
		}
		else
		{
			fc_retval = 0.0;
		}

		/* 如有需要，返回反向值 */
		if (fc_inverse)
			fc_retval = -fc_retval;
	}
	else
	{
		NDBOX	   *fc_query = PG_GETARG_NDBOX_P(1);

		switch (fc_strategy)
		{
			case CubeKNNDistanceTaxicab:
				fc_retval = DatumGetFloat8(DirectFunctionCall2(distance_taxicab,
															PointerGetDatum(fc_cube), PointerGetDatum(fc_query)));
				break;
			case CubeKNNDistanceEuclid:
				fc_retval = DatumGetFloat8(DirectFunctionCall2(cube_distance,
															PointerGetDatum(fc_cube), PointerGetDatum(fc_query)));
				break;
			case CubeKNNDistanceChebyshev:
				fc_retval = DatumGetFloat8(DirectFunctionCall2(distance_chebyshev,
															PointerGetDatum(fc_cube), PointerGetDatum(fc_query)));
				break;
			default:
				elog(ERROR, "unrecognized cube strategy number: %d", fc_strategy);
				fc_retval = 0;		/* 保持编译器安静 */
				break;
		}
	}
	PG_RETURN_FLOAT8(fc_retval);
}

static double fc_distance_1D(double fc_a1, double fc_a2, double fc_b1, double fc_b2)
{
	/* 区间 (a) 完全在 (b) 的左侧 */
	if ((fc_a1 <= fc_b1) && (fc_a2 <= fc_b1) && (fc_a1 <= fc_b2) && (fc_a2 <= fc_b2))
		return (Min(fc_b1, fc_b2) - Max(fc_a1, fc_a2));

	/* 区间 (a) 完全在 (b) 的右侧 */
	if ((fc_a1 > fc_b1) && (fc_a2 > fc_b1) && (fc_a1 > fc_b2) && (fc_a2 > fc_b2))
		return (Min(fc_a1, fc_a2) - Max(fc_b1, fc_b2));

	/* 其余都是各种交集 */
	return 0.0;
}

/* 测试一个盒子是否也是一个点 */
Datum cube_is_point(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_cube = PG_GETARG_NDBOX_P(0);
	bool		fc_result;

	fc_result = fc_cube_is_point_internal(fc_cube);
	PG_FREE_IF_COPY(fc_cube, 0);
	PG_RETURN_BOOL(fc_result);
}

static bool fc_cube_is_point_internal(NDBOX *fc_cube)
{
	int			fc_i;

	if (IS_POINT(fc_cube))
		return true;

	/*
	 * 即使未设置点标志，所有的左下坐标可能也与右上坐标匹配，
	 * 使得该值实际上是一个点。这样的值在当前代码中不会出现 - 
	 * 如果合适，点标志总是会被设置 - 但它们可能在从pre-9.4版本升级的
	 * 集群中存在。
	 */
	for (fc_i = 0; fc_i < DIM(fc_cube); fc_i++)
	{
		if (LL_COORD(fc_cube, fc_i) != UR_COORD(fc_cube, fc_i))
			return false;
	}
	return true;
}

/* 返回数据结构中正在使用的维度 */
Datum cube_dim(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_c = PG_GETARG_NDBOX_P(0);
	int			fc_dim = DIM(fc_c);

	PG_FREE_IF_COPY(fc_c, 0);
	PG_RETURN_INT32(fc_dim);
}

/* 返回特定的归一化 LL 坐标 */
Datum cube_ll_coord(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_c = PG_GETARG_NDBOX_P(0);
	int			fc_n = PG_GETARG_INT32(1);
	double		fc_result;

	if (DIM(fc_c) >= fc_n && fc_n > 0)
		fc_result = Min(LL_COORD(fc_c, fc_n - 1), UR_COORD(fc_c, fc_n - 1));
	else
		fc_result = 0;

	PG_FREE_IF_COPY(fc_c, 0);
	PG_RETURN_FLOAT8(fc_result);
}

/* 返回特定的归一化 UR 坐标 */
Datum cube_ur_coord(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_c = PG_GETARG_NDBOX_P(0);
	int			fc_n = PG_GETARG_INT32(1);
	double		fc_result;

	if (DIM(fc_c) >= fc_n && fc_n > 0)
		fc_result = Max(LL_COORD(fc_c, fc_n - 1), UR_COORD(fc_c, fc_n - 1));
	else
		fc_result = 0;

	PG_FREE_IF_COPY(fc_c, 0);
	PG_RETURN_FLOAT8(fc_result);
}

/*
 * 函数返回立方体坐标。
 * 从 1 到 DIM 的数字表示第一个角的坐标。
 * 从 DIM+1 到 2*DIM 的数字表示第二个角的坐标。
 */
Datum cube_coord(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_cube = PG_GETARG_NDBOX_P(0);
	int			fc_coord = PG_GETARG_INT32(1);

	if (fc_coord <= 0 || fc_coord > 2 * DIM(fc_cube))
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
				 errmsg("cube index %d is out of bounds", fc_coord)));

	if (IS_POINT(fc_cube))
		PG_RETURN_FLOAT8(fc_cube->x[(fc_coord - 1) % DIM(fc_cube)]);
	else
		PG_RETURN_FLOAT8(fc_cube->x[fc_coord - 1]);
}


/*----
 * 这个函数的工作方式类似于 cube_coord()，但重新排列坐标的方式
 * 适合支持使用 KNN-GiST 的坐标排序。出于历史原因，该扩展允许我们以
 * ((2,1),(1,2)) 形式创建立方体，而不是将这样的立方体标准化为
 * ((1,1),(2,2))，它以原始方式存储立方体。但是，为了从索引中按某个
 * 维度获得排序的立方体，而不需要显式的排序步骤，我们需要这个
 * 不依赖于表示的坐标获取器。此外，索引数据集可能包含不同维度数量的
 * 立方体。因此，这个坐标获取器应该能够独立于立方体维度数量
 * 返回特定维度的上下界。此外，KNN-GiST 仅支持升序排序。为了
 * 支持降序排序，当给定负坐标时，此函数返回值的反向。
 *
 * 长话短说，这个函数使用以下意义的坐标：
 * # (2 * N - 1) -- 第 N 维的下界，
 * # (2 * N) -- 第 N 维的上界，
 * # - (2 * N - 1) -- 第 N 维下界的负值，
 * # - (2 * N) -- 第 N 维上界的负值。
 *
 * 当给定的坐标超过立方体维度的数量时，则返回 0
 * （复制可变长度立方体的 GiST 索引逻辑）。
 */
Datum cube_coord_llur(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_cube = PG_GETARG_NDBOX_P(0);
	int			fc_coord = PG_GETARG_INT32(1);
	bool		fc_inverse = false;
	float8		fc_result;

	/* 0 是唯一不支持的坐标值 */
	if (fc_coord == 0)
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
				 errmsg("zero cube index is not defined")));

	/* 对于负坐标返回反向值 */
	if (fc_coord < 0)
	{
		fc_coord = -fc_coord;
		fc_inverse = true;
	}

	if (fc_coord <= 2 * DIM(fc_cube))
	{
		/* 维度索引 */
		int			fc_index = (fc_coord - 1) / 2;

		/* 这是否是上界（否则为下界） */
		bool		fc_upper = ((fc_coord - 1) % 2 == 1);

		if (IS_POINT(fc_cube))
		{
			fc_result = fc_cube->x[fc_index];
		}
		else
		{
			if (fc_upper)
				fc_result = Max(fc_cube->x[fc_index], fc_cube->x[fc_index + DIM(fc_cube)]);
			else
				fc_result = Min(fc_cube->x[fc_index], fc_cube->x[fc_index + DIM(fc_cube)]);
		}
	}
	else
	{
		/*
		 * 如果坐标超出边界，则返回零。这复制了立方体在 GiST
		 * 索引期间如何扩展低维度数量的逻辑。
		 */
		fc_result = 0.0;
	}

	/* 如有必要，返回反向值 */
	if (fc_inverse)
		fc_result = -fc_result;

	PG_RETURN_FLOAT8(fc_result);
}

/* 在至少 n 个维度上通过半径增加或减少盒子的大小。 */
Datum cube_enlarge(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_a = PG_GETARG_NDBOX_P(0);
	double		fc_r = PG_GETARG_FLOAT8(1);
	int32		fc_n = PG_GETARG_INT32(2);
	NDBOX	   *fc_result;
	int			fc_dim = 0;
	int			fc_size;
	int			fc_i,
				fc_j;

	if (fc_n > CUBE_MAX_DIM)
		fc_n = CUBE_MAX_DIM;
	if (fc_r > 0 && fc_n > 0)
		fc_dim = fc_n;
	if (DIM(fc_a) > fc_dim)
		fc_dim = DIM(fc_a);

	fc_size = CUBE_SIZE(fc_dim);
	fc_result = (NDBOX *) palloc0(fc_size);
	SET_VARSIZE(fc_result, fc_size);
	SET_DIM(fc_result, fc_dim);

	for (fc_i = 0, fc_j = fc_dim; fc_i < DIM(fc_a); fc_i++, fc_j++)
	{
		if (LL_COORD(fc_a, fc_i) >= UR_COORD(fc_a, fc_i))
		{
			fc_result->x[fc_i] = UR_COORD(fc_a, fc_i) - fc_r;
			fc_result->x[fc_j] = LL_COORD(fc_a, fc_i) + fc_r;
		}
		else
		{
			fc_result->x[fc_i] = LL_COORD(fc_a, fc_i) - fc_r;
			fc_result->x[fc_j] = UR_COORD(fc_a, fc_i) + fc_r;
		}
		if (fc_result->x[fc_i] > fc_result->x[fc_j])
		{
			fc_result->x[fc_i] = (fc_result->x[fc_i] + fc_result->x[fc_j]) / 2;
			fc_result->x[fc_j] = fc_result->x[fc_i];
		}
	}
	/* dim > a->dim 仅当 r > 0 */
	for (; fc_i < fc_dim; fc_i++, fc_j++)
	{
		fc_result->x[fc_i] = -fc_r;
		fc_result->x[fc_j] = fc_r;
	}

	/*
	 * 检查结果是否实际上是一个点，并相应地在数据项中设置标志。
	 * （我们不费心将其重新分配得更小）
	 */
	if (fc_cube_is_point_internal(fc_result))
	{
		fc_size = POINT_SIZE(fc_dim);
		SET_VARSIZE(fc_result, fc_size);
		SET_POINT_BIT(fc_result);
	}

	PG_FREE_IF_COPY(fc_a, 0);
	PG_RETURN_NDBOX_P(fc_result);
}

/* 创建一个一维盒子，其上下坐标相同 */
Datum cube_f8(PG_FUNCTION_ARGS)
{
	double		fc_x = PG_GETARG_FLOAT8(0);
	NDBOX	   *fc_result;
	int			fc_size;

	fc_size = POINT_SIZE(1);
	fc_result = (NDBOX *) palloc0(fc_size);
	SET_VARSIZE(fc_result, fc_size);
	SET_DIM(fc_result, 1);
	SET_POINT_BIT(fc_result);
	fc_result->x[0] = fc_x;

	PG_RETURN_NDBOX_P(fc_result);
}

/* 创建一个一维盒子 */
Datum cube_f8_f8(PG_FUNCTION_ARGS)
{
	double		fc_x0 = PG_GETARG_FLOAT8(0);
	double		fc_x1 = PG_GETARG_FLOAT8(1);
	NDBOX	   *fc_result;
	int			fc_size;

	if (fc_x0 == fc_x1)
	{
		fc_size = POINT_SIZE(1);
		fc_result = (NDBOX *) palloc0(fc_size);
		SET_VARSIZE(fc_result, fc_size);
		SET_DIM(fc_result, 1);
		SET_POINT_BIT(fc_result);
		fc_result->x[0] = fc_x0;
	}
	else
	{
		fc_size = CUBE_SIZE(1);
		fc_result = (NDBOX *) palloc0(fc_size);
		SET_VARSIZE(fc_result, fc_size);
		SET_DIM(fc_result, 1);
		fc_result->x[0] = fc_x0;
		fc_result->x[1] = fc_x1;
	}

	PG_RETURN_NDBOX_P(fc_result);
}

/* 在现有立方体中添加一个维度，新坐标的值相同 */
Datum cube_c_f8(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_cube = PG_GETARG_NDBOX_P(0);
	double		fc_x = PG_GETARG_FLOAT8(1);
	NDBOX	   *fc_result;
	int			fc_size;
	int			fc_i;

	if (DIM(fc_cube) + 1 > CUBE_MAX_DIM)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("can't extend cube"),
				 errdetail("A cube cannot have more than %d dimensions.",
						   CUBE_MAX_DIM)));

	if (IS_POINT(fc_cube))
	{
		fc_size = POINT_SIZE((DIM(fc_cube) + 1));
		fc_result = (NDBOX *) palloc0(fc_size);
		SET_VARSIZE(fc_result, fc_size);
		SET_DIM(fc_result, DIM(fc_cube) + 1);
		SET_POINT_BIT(fc_result);
		for (fc_i = 0; fc_i < DIM(fc_cube); fc_i++)
			fc_result->x[fc_i] = fc_cube->x[fc_i];
		fc_result->x[DIM(fc_result) - 1] = fc_x;
	}
	else
	{
		fc_size = CUBE_SIZE((DIM(fc_cube) + 1));
		fc_result = (NDBOX *) palloc0(fc_size);
		SET_VARSIZE(fc_result, fc_size);
		SET_DIM(fc_result, DIM(fc_cube) + 1);
		for (fc_i = 0; fc_i < DIM(fc_cube); fc_i++)
		{
			fc_result->x[fc_i] = fc_cube->x[fc_i];
			fc_result->x[DIM(fc_result) + fc_i] = fc_cube->x[DIM(fc_cube) + fc_i];
		}
		fc_result->x[DIM(fc_result) - 1] = fc_x;
		fc_result->x[2 * DIM(fc_result) - 1] = fc_x;
	}

	PG_FREE_IF_COPY(fc_cube, 0);
	PG_RETURN_NDBOX_P(fc_result);
}

/* 在现有立方体中添加一个维度 */
Datum cube_c_f8_f8(PG_FUNCTION_ARGS)
{
	NDBOX	   *fc_cube = PG_GETARG_NDBOX_P(0);
	double		fc_x1 = PG_GETARG_FLOAT8(1);
	double		fc_x2 = PG_GETARG_FLOAT8(2);
	NDBOX	   *fc_result;
	int			fc_size;
	int			fc_i;

	if (DIM(fc_cube) + 1 > CUBE_MAX_DIM)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("can't extend cube"),
				 errdetail("A cube cannot have more than %d dimensions.",
						   CUBE_MAX_DIM)));

	if (IS_POINT(fc_cube) && (fc_x1 == fc_x2))
	{
		fc_size = POINT_SIZE((DIM(fc_cube) + 1));
		fc_result = (NDBOX *) palloc0(fc_size);
		SET_VARSIZE(fc_result, fc_size);
		SET_DIM(fc_result, DIM(fc_cube) + 1);
		SET_POINT_BIT(fc_result);
		for (fc_i = 0; fc_i < DIM(fc_cube); fc_i++)
			fc_result->x[fc_i] = fc_cube->x[fc_i];
		fc_result->x[DIM(fc_result) - 1] = fc_x1;
	}
	else
	{
		fc_size = CUBE_SIZE((DIM(fc_cube) + 1));
		fc_result = (NDBOX *) palloc0(fc_size);
		SET_VARSIZE(fc_result, fc_size);
		SET_DIM(fc_result, DIM(fc_cube) + 1);
		for (fc_i = 0; fc_i < DIM(fc_cube); fc_i++)
		{
			fc_result->x[fc_i] = LL_COORD(fc_cube, fc_i);
			fc_result->x[DIM(fc_result) + fc_i] = UR_COORD(fc_cube, fc_i);
		}
		fc_result->x[DIM(fc_result) - 1] = fc_x1;
		fc_result->x[2 * DIM(fc_result) - 1] = fc_x2;
	}

	PG_FREE_IF_COPY(fc_cube, 0);
	PG_RETURN_NDBOX_P(fc_result);
}
